Math 560: Optimization

Prof. Andrew Ross

Fall Semester 2014

Basic Information

Note: this syllabus is temporary, and may change up to the first day of class.
This version posted on: 2014-08-25

The official course title is "Introduction to Optimization Theory". However, we will try to split our time evenly between applications/modeling, theory, and methods.

Mathematical optimization is the science of finding the best (e.g. lowest cost) solution to a problem. Often, we also try to prove that it is the best, or that it is within some small percentage of the best solution. Some common examples are:

Since you have had the prerequisite courses, you are familiar with finding the minimum or maximum of a function using derivatives (like in first-semester calculus), and finding the minimum or maximum of a function of two or three variables (like in third-semester calculus). In this course, we will be working with thousands of variables--real applications can use millions of variables. Of course, we don't solve problems like that by hand. In our course, we will learn the methods people have developed for computers to solve such large problems.

Official Course Catalog Entry

An introduction to various aspects of optimization theory, including linear and nonlinear programming, primal dual methods, calculus of variations, optimal control theory, sensitivity analysis and numerical methods.

Prerequisites

Completion of courses in elementary linear algebra/matrix algebra and multivariable calculus is assumed.
Some experience using Excel, Mathematica, Maple, or Matlab/Octave/SciLab will also be very helpful, but it is not strictly a prerequisite.

Follow-up courses: Math 436 Numerical Analysis, Math 419W/519 Stochastic Math Models, various statistics classes.

Related courses:

  • Convex Optimization lecture videos from Stanford

    Class Meetings

    CRN 16959: Tue, Thu 4:00pm-5:15pm in Pray-Harrold 503
    Brief schedule: 3 credit hours.

    Class meetings will be mostly interactive lectures and computer lab work, with some time to discuss homework.

    Instructor information

    Professor Andrew Ross
    Pray-Harrold 515m
    andrew.ross@emich.edu
    http://people.emich.edu/aross15/
    (734) 487-1658, but I strongly prefer e-mail instead of phone contact.
    Math department main office: Pray-Harrold 515, (734) 487-1444

    Office Hours and other help

    Here is my complete schedule. 
    Mon/Wed:
    10:30-11:00 Office hours 
    11:00-12:15 Math 360-0 in Pray-Harrold 503
    12:15-12:45 Office hours and lunch
Tue/Thu:
   11:45-12:45 research meeting
    1:30-2:00 Office hours in my office
    2:00-3:15 Math 360-1 in Pray-Harrold 503
    3:15-4:00 Office hours in PH 503 and/or my office
    4:00-5:15 Math 560 in Pray-Harrold 503
    5:15-5:30 Office hours in PH 503 and/or my office
Fri:
  No official office hours, but I'm often on campus.
  E-mail me to make an appointment, or drop by.

    I am also happy to make appointments if you cannot come to the general office hours. Please send me e-mail to arrange an appointment.

    Many assignments in this course will be in the form of papers, which I want to be well written. Please consult with The Writing Center for help in tuning up your writing.

    Required materials

    We will be using pieces from the following textbooks, which are ELECTRONICALLY FREELY AVAILABLE to EMU students through our campus library:

    Other suggested (not required) textbooks are "Operations Research: Applications and Algorithms (4th revised edition)" by Wayne Winston (2004), and "Introduction to Operations Research, 10th edition" by Hillier and Lieberman. These are more undergraduate-level texts, which provide a gentler introduction to the subject but can get stuck in by-hand calculations. The high cost is why they are suggested but not required.

    We will also be using software. At least one of the following, and possibly more, is required:

    Course Web Page

    We will use the EMU-Online system. You are expected to keep an eye on your scores using the system, and get extra help if your scores indicate the need.

    Supplementary Materials

    Here are some handy web sites: Here are some other optimization books: Other books related to optimization, but not really our main focus: Books on Optimization Models:

    Blogs

    Here are some of the blogs that relate to our class:

    Course Content

    Course Goals

    Our primary goal is to teach you to be a good (or great!) optimizer. To be a good optimizer, you need:

    Here is an idealized, pie-in-the-sky list of Student Learning Outcomes for this course: Students will be able to:
    1. Formulate common LPs in software and symbolically
    2. Formulate common IPs in software and symbolically
    3. Explain the Fundamental Theorem of LP
    4. Explain the roles of convexity in NLPs
    5. Explain meta-heuristics: Evolutionary, Simulated Annealing, and perhaps others
    6. Explain classic unconstrained NLP solution methods: line search, Steepest Descent, Newton, Quasi-Newton
    7. Explain the Simplex Method
    8. Explain duality and sensitivity analysis for LPs; column generation
    9. Explain Lagrange Multipliers/the KKT conditions and sensitivity analysis for constrained NLPs
    10. Explain constrained NLP solution methods
    11. Explain interior-point methods for LP
    12. Explain branch-and-bound for IPs; tight formulations, symmetry-breaking; branch-and-cut
    13. Consider factors affecting speed of unconstrained NLP solution: Conditioning, use of derivatives, algorithm convergence order/rate, etc.
    14. Recall the names of other optimization topics: Constraint Programming, Stochastic Programming, Robust Programming, Dynamic Programming, Calculus of Variations, Optimal Control
    15. Take an optimization project from initial concept to formulation(s) and solution(s) including algorithmic concerns, and report/presentation.
    and we will take them in that order, mostly.

    Outline/schedule

    Many classes in optimization theory start with linear problems and solution methods, then proceed to nonlinear problems, because linear problems and solution methods are simpler. Other classes start with nonlinear, because then linear is just a special case. We will start with mostly nonlinear problems and solution methods because then you will have a wide base of ideas to do the first (mid-semester) project.

    Grading Policies

    Attendance

    Regular attendance is strongly recommended. There will be material presented in class that is not in the textbook(s), yet will be very useful. Similarly, there are things in the textbook(s) that are might not be covered in class, but are still very useful. If you must miss a class, arrange to get a copy of the notes from someone, and arrange for someone to ask your questions for you.

    My lectures and discussions mostly use the document camera, along with demonstrations in Excel and other mathematical software. I do not usually have PowerPoint-like presentations, and thus cannot hand out copies of slides.

    Homework

    Homework will be assigned about once a week. It will sometimes be a small problem set designed to help you understand the behavior of math models. Other times, it will involve writing up a little paper on an assigned topic. All homework should be typed.

    Homework papers should be submitted on-line via EMU-Online, unless otherwise noted in the assignment.

    Exams

    There will be no exams, unless the class demonstrates an unwillingness to be motivated any other way.

    Project(s)

    Instead of exams, we will have two projects. Your results for each will reported in a paper and a presentation to the class. You may work by yourself or in a team of 2 people, but no groups larger than 2 will be allowed. You may switch project partners at your will. Your project grades will each be split into roughly: 10 percent for the project proposal (due 2 weeks before the project), 80 percent for the written paper and actual work, and 10 percent for the presentation (subject to change). The presentations for the second project will be made during the time slot reserved for the final exam.

    Overall Grades

    No scores will be dropped, unless a valid medical excuse with evidence is given. In the unfortunate event of a medical need, the appropriate grade or grades may be dropped entirely (at the professor's discretion), rather than giving a make-up. You are highly encouraged to still complete the relevant assignments and consult with me during office hours to ensure you know the material.

    Your final score will be computed as follows: Once final scores are computed, a curve will be applied.

    General Caveat

    The instructor reserves the right to make changes to this syllabus throughout the semester. Notification will be given in class or by e-mail or both. If you miss class, it is your responsibility to find out about syllabus and schedule changes, especially the due dates and times of projects, assignments, or presentations.

    Advice from previous students

    Last time I taught the course, I asked my students to give advice to you, future students, based on their experiences in my course. Here are some of the highlights:

    Standard University Policies

    Religious Holy Days

    I support students' right to observe religious holidays without penalty. To the best of my ability, I will schedule exams to not conflict with major religions' holidays. Students are to provide advance notice to the instructor in order to make up work, including examinations that they miss as a result of their absence from class due to observance of religious holidays. If satisfactory arrangements cannot be made, the student may appeal to the head of the department.

    Academic Honesty

    Academic dishonesty, including all forms of cheating and/or plagiarism, will not be tolerated in this class. Penalties for an act of academic dishonesty may range from receiving a failing grade for a particular assignment to receiving a failing grade for the entire course. In addition, you may be referred to the Office of Student Judicial Services for discipline that can result in either a suspension or permanent dismissal. The Student Conduct Code contains detailed definitions of what constitutes academic dishonesty, but if you are not sure about whether something you’re doing would be considered academic dishonesty, consult with the instructor.

    Classroom Behavior

    Students are expected to abide by the Student Conduct Code and assist in creating an environment that is conducive to learning and protects the rights of all members of the University community. Incivility and disruptive behavior will not be tolerated and may result in a request to leave class and referral to the Office of Student Judicial Services (SJS) for discipline. Examples of inappropriate classroom conduct include repeatedly arriving late to class, using a cellular telephone, or talking while others are speaking. You may access the Code online at www.emich.edu/sjs.

    Special Needs Accomodations

    If you wish to be accommodated for your disability, EMU Board of Regents policy #8.3 requires that you first register with the Access Services Office (ASO) in room 203 King Hall. You may contact ASO by telephone at (734) 487-2470. Students with disabilities are encouraged to register with ASO promptly as you will only be accommodated from the date you register with them forward. No retroactive accommodations are possible.

    Student and Exchange VISitors (SEVIS)

    The Student Exchange Visitor Information System (SEVIS) requires F and J students to report the following to the Office of International Students, 229 King Hall within ten (10) days of the event: Prior permission from OIS is needed for the following: Failure to report may result in the termination of your SEVIS record and even arrest and deportation. If you have questions or concerns, contact the OIS at 487-3116, not your instructor. Also, see the EMU SEVIS page.